#include "HeapSort.h"

// 调整了一下的堆排序
// 在能交换整型的情况下,试着使用了一下之前教的分割交换,现在的交换函数可以使用在多种数据类型的交换了

// 交换算法

void Swap (void* x , void* y , int size)
{

    char tmp = 0 ;

    for (int i = 0 ; i < size ; i++)
    {

        tmp = *((char*) x + i) ;

        *((char*) x + i) = *((char*) y + i) ;

        *((char*) y + i) = tmp ;

    }

}

// 向上调整算法

void AdjustUp1 (HPDataType* arr , int child , int size)
{

    int parent = (child - 1) / 2 ;

    while (child > 0)
    {
        
        // 建大堆: <
        // 建小堆: >
        // arr [parent] < arr [child]

        // 建大堆: !
        // 建小堆:

        if (arr [parent] < arr [child])
        {

            Swap (&arr [parent] , &arr [child] , size) ;

            child = parent ;

            parent = (child - 1) / 2 ;

        }

        else
        {

            break ;

        }


    }

}

// 向下调整算法

void AdjustDown1 (HPDataType* arr , int parent , int n , int size)
{

    int child = parent * 2 + 1 ;

    while (child < n)
    {

        // 大堆: <
        // 小堆: >
        // arr [child] < arr [child + 1]

        // 大堆: !
        // 小堆: 

        if (child + 1 < n && !Cmp_Int (&arr [child] , &arr [child + 1]))
        {

            child++ ;

        }

        // 大堆: <
        // 小堆: >
        // arr [parent] < arr [child]

        // 大堆: ! 
        // 小堆:

        if (!Cmp_Int (&arr [parent] , &arr [child]))
        {

            Swap (&arr [parent] , &arr [child] , size) ;

            parent = child ;

            child = parent * 2 + 1 ;

        }

        else
        {

            break ;

        }

    }

}

// 堆排序

void HeapSort (HPDataType* arr , int n , int size)
{

    // // 向上调整算法

    // for (int i = 0 ; i < n ; i++)
    // {

    //     AdjustUp1 (arr , i , size) ;

    // }

    // 向下调整算法

    for (int i = (n - 1 - 1) / 2 ; i >= 0 ; i--)
    {

        AdjustDown1 (arr , i , n , size) ;

    }

    int count = n - 1 ;

    for (int i = 0 ; i < n ; i++)
    {

        Swap (&arr [0] , &arr [count] , size) ;

        AdjustDown1 (arr , 0 , count , size) ;

        count-- ;

    }

}

// 打印数据

void HeapPrint (HPDataType* arr , int n)
{

    for (int i = 0 ; i < n ; i++)
    {

        printf ("%d " , arr [i]) ;

    }

    printf ("\n") ;

}